home *** CD-ROM | disk | FTP | other *** search
/ Czech Logic, Card & Gambling Games / Logické hry.iso / hry / Piskvorky / source / pbrain / piskcomp.cpp < prev    next >
C/C++ Source or Header  |  2006-03-29  |  19KB  |  778 lines
  1. /*
  2.   (C) 2000-2005  Petr Lastovicka
  3.  
  4.   contents of this file are subject to the Reciprocal Public License ("RPL")
  5. */
  6. #include <windows.h>
  7. #pragma hdrstop
  8. #include <assert.h>
  9. #include "board.h"
  10.  
  11. #define EVAL_RAND1 20  //randomness
  12. #define EVAL_RAND2 30  //maximal randomness for low evaluation
  13. #define AHEAD_DEPTH 4  //depth search to find good total evaluation
  14. #define AHEAD_IRRELEVANCE 3
  15. #define NUM_GOOD0 100
  16. #define NUM_GOOD1 30
  17. #define OFFENSIVE 1   
  18. #define DEFEND_HIGHEVAL 70
  19.  
  20. int
  21.  height2,   //height+2
  22.  moves,     //moves counter
  23.  depth,     //maximal recursion depth (is increased until timeout)
  24.  diroff[9];    //pointer difference to adjacent squares
  25.  
  26. int 
  27.  winEval[MwinMoves], //evaluation of winMoves1
  28.  winMoveDepth[2],    //depth of win combination
  29.  sum[2],    //total evaluation for both players
  30.  dpth=0;    //current recursion depth
  31.  
  32. Psquare
  33.  board=0,        //board array
  34.  boardb, boardk, //pointer to the beginning and end of board
  35.  loss4,          //opponent can win through foursomes
  36.  resultMove,     //the best move
  37.  highestEval,    //square which has the best evaluation
  38.  lastMove,
  39.  holdMove;
  40.  
  41. Psquare
  42.  goodMoves[4][2],     //linked lists of highly evaluated squares, for both players
  43.  winMoves1[MwinMoves],//buffer for win combination
  44.  *UwinMoves,
  45.  winMove[2],     //the first move of win combination
  46.  bestMove;      
  47.  
  48. bool
  49.  depthReached,   //depth has beeb reached (and can be increased)
  50.  attackDone,defendDone,defendDone1,testDone,
  51.  carefulAttack,carefulDefend;
  52.  
  53. const int priority[][3]={{0,1,1},{H10,H11,H12},{H20,H21,H22},{H30,H31,0},{H4,0,0}};
  54.  
  55. #ifdef DEBUG
  56.  int mt;       //curMoves buffer utilization
  57.  int resulty;  //win/loss/unknown
  58. #endif
  59. int benchmark;//counter of searched moves
  60.  
  61. //-------------------------------------------------------------------
  62. signed char data[]={
  63.  15,1, 4,0,0,0,1,1,2,3,2,2,4,2,5,3,3,4,3,3,5,5,4,3,3,6,4,5,6,5,5,4, 3,1,
  64.  11,1, 1,1,0,0,2,2,3,2,3,3,1,3,2,4,1,5,3,3,3,2,5,1, 4,3,
  65.  11,1, 1,0,0,0,1,1,3,2,2,2,2,3,3,3,2,4,2,5,1,5,1,4, 0,3,
  66.   9,1, 0,0,0,3,0,1,1,2,0,2,2,3,3,3,3,4,2,4, 1,1,
  67.   9,1, 1,1,0,0,2,2,3,2,3,3,2,3,1,4,1,3,1,5, 2,4,
  68.   9,1, 1,0,0,0,0,1,1,1,2,2,2,1,2,3,1,2,0,3, 1,4,
  69.   9,1, 0,0,2,0,1,0,1,1,0,1,2,2,3,2,3,3,2,3, 0,2,
  70.   9,1, 1,1,0,0,2,2,0,2,2,1,3,1,1,2,1,3,0,3, 3,0,
  71.   9,1, 0,0,2,0,1,1,1,2,2,1,1,4,3,2,4,3,2,3, 0,1,
  72.   8,1, 0,2,1,1,1,2,2,0,2,2,3,0,3,1,3,2, 4,0,
  73.   8,1, 1,1,3,0,0,2,3,1,1,3,2,2,2,3,1,4, 3,3,
  74.   7,1, 0,0,1,1,0,1,2,2,3,2,3,3,2,3, 0,2,
  75.   7,1, 3,2,2,1,2,2,1,1,1,0,0,0,0,1, 1,2,
  76.   7,1, 0,0,0,1,1,0,0,3,2,1,3,2,1,2, 1,-1,
  77.   7,1, 1,0,0,1,0,2,2,2,2,1,3,2,5,2, 3,0,
  78.   7,1, 0,0,0,1,2,0,0,3,2,1,1,3,1,2, 2,3,
  79.   7,1, 1,0,0,0,0,1,1,1,2,2,1,2,1,3, 2,3,
  80.   7,1, 0,1,1,1,2,0,0,2,1,2,3,4,2,3, 2,1,
  81.   6,1, 1,0,0,0,0,2,1,1,3,3,2,2, 1,-1,
  82.   6,1, 1,0,0,0,1,1,2,1,2,2,1,2, 0,-1,
  83.   6,1, 0,0,1,0,2,1,3,1,3,2,2,2, 1,-1,
  84.   6,1, 3,0,0,0,1,1,2,1,2,2,1,2, -1,0,
  85.   6,1, 0,0,1,1,3,1,2,2,4,3,3,3, 2,4,
  86.   6,1, 0,2,0,0,1,1,1,2,2,2,2,1, 3,0,
  87.   6,1, 2,1,0,0,2,2,0,1,2,3,1,2, 2,0,
  88.   6,1, 2,1,0,0,1,3,0,1,2,3,1,2, 2,0,
  89.   5,2, 2,2,0,0,1,0,1,1,0,1, 2,1,1,2,
  90.   5,1, 0,0,2,1,0,1,2,3,1,2, 1,3,
  91.   5,1, 1,0,0,0,1,1,1,2,2,1, 1,-1,
  92.   5,1, 1,1,1,0,0,2,1,3,1,2, 2,2,
  93.   5,1, 1,0,0,0,0,1,1,1,2,3, 2,2,
  94.   5,2, 0,0,1,1,1,2,0,1,2,1, 2,0,3,0,
  95.   5,1, 0,2,1,0,2,0,2,1,1,1, -1,3,
  96.   5,1, 1,0,1,1,0,1,2,1,3,2, 2,-1,
  97.   5,1, 1,1,0,0,2,1,0,2,3,1, 0,1,
  98.   5,2, 1,1,0,0,2,1,1,3,1,2, 0,1,3,1,
  99.   5,2, 1,0,0,0,0,1,2,1,1,1, 1,2,-1,2,
  100.   5,1, 1,0,1,2,0,1,3,2,2,1, 2,-1,
  101.   5,2, 0,1,1,2,2,1,3,0,0,3, 1,1,0,2,
  102.   5,1, 2,0,0,2,1,1,1,2,2,2, 0,0,
  103.   5,1, 0,0,1,1,1,0,1,2,0,2, 0,1,
  104.   4,1, 1,0,0,1,1,3,1,2, -1,0,
  105.   4,1, 1,0,0,1,1,1,1,2, -1,0,
  106.   4,1, 1,0,1,1,0,2,2,2, 0,0,
  107.   4,1, 2,0,0,0,0,2,1,1, 2,2,
  108.   4,1, 0,0,1,1,3,1,2,2, 3,3,
  109.   4,2, 2,0,0,0,2,2,1,1, 0,-1,1,-1,
  110.   4,1, 2,0,0,0,2,1,1,1, 2,2,
  111.   4,1, 1,0,0,1,2,0,1,2, -1,0,
  112.   4,1, 1,0,0,0,0,2,1,1, -1,-1,
  113.   4,1, 1,0,0,1,2,2,1,2, -1,0,
  114.   4,1, 0,0,1,1,2,1,2,2, 3,3,
  115.   3,1, 0,1,0,0,1,0, 1,1,
  116.   3,1, 0,0,2,0,1,1, 2,2,
  117.   3,4, 1,0,0,1,1,2, 0,2,0,0,2,0,2,2,
  118.   3,1, 1,2,0,0,1,1, 1,3,
  119.   3,1, 1,0,0,0,1,1, 1,2,
  120.   3,1, 0,0,0,2,0,1, 0,-1,
  121.   3,1, 0,0,2,1,1,1, 2,2,
  122.   3,1, 0,0,0,1,1,2, 1,1,
  123.   3,2, 0,0,2,2,1,1, 2,1,1,2,
  124.   3,1, 0,1,3,0,2,0, 1,1,
  125.   3,1, 0,0,2,1,2,2, 1,1,
  126.   3,4, 0,0,1,1,2,2, 1,-1,-1,1,3,1,1,3,
  127.   3,1, 0,0,0,2,1,2, 1,0,
  128.   3,2, 1,0,0,3,1,2, 2,3,1,1,
  129.   3,2, 0,0,0,3,0,2, 1,3,-1,3,
  130.   3,1, 0,0,0,3,1,2, 1,1,
  131.   3,1, 1,0,0,2,1,2, 1,1,
  132.   3,1, 0,0,2,1,1,2, 0,2,
  133.   3,1, 0,0,2,2,1,2, 0,1,
  134.   3,1, 0,0,3,3,2,2, 1,1,
  135.   3,1, 0,0,3,2,2,2, 1,1,
  136.   3,1, 0,0,3,1,2,2, 3,3,
  137.   3,6, 0,0,1,0,2,0, 1,1,1,-1,0,2,0,-2,2,2,2,-2,
  138.   3,3, 0,0,3,2,2,1, 1,0,1,1,0,1,
  139.   2,3, 0,0,1,1, 0,2,2,0,1,2,
  140.   2,8, 0,0,1,0, -1,-1,0,-1,1,-1,2,-1,-1,1,0,1,1,1,2,1,
  141.   2,2, 0,0,2,2, 1,3,3,1,
  142.   1,8, 0,0, -1,0,1,0,0,1,0,-1, 1,1,-1,1,1,-1,-1,-1,
  143.   0,0
  144. };
  145. //-------------------------------------------------------------------
  146. Psquare Square(int x, int y) //indexed from zero
  147. {
  148.   return boardb + x*height2+(y+1);
  149. }
  150. //-------------------------------------------------------------------
  151. struct PR2 { short h[2]; };
  152. PR2 K[262144];       //evaluation for all combinations of 9 squares
  153. static int comb[10]; //current combination
  154. static PR2 *ind;     //write position in array K
  155. static int n[4];     //number of empty fields, stones and borders
  156. //-------------------------------------------------------------------
  157. void gen2(int *pos)
  158. {
  159.   int *pb,*pe;
  160.   int n[4],a1,a2;
  161.   int s;
  162.   bool six[2];
  163.   
  164.   if(pos==comb+9){
  165.     a1=a2=0;
  166.     if(comb[4]==0){ //the middle square must be empty
  167.       n[1]=::n[1]; n[2]=::n[2]; n[3]=::n[3];
  168.       six[0]=six[1]=false;
  169.       pb=comb;
  170.       pe=pb+4;
  171.       while(pe!=comb+9){
  172.         if(!n[3]){ //must not be outside the board
  173.           if(!n[2]){
  174.             //my chances
  175.             s=0;
  176.             if(!*pb && pe[1]<2 && pb!=comb+4){
  177.               s++;
  178.               if(!*pe && pe!=comb+4) s++;
  179.             }
  180.             if(info_exact5==1 && n[1]==4 && 
  181.               (pe<comb+8 && pe[1]==1 || pb>comb && pb[-1]==1)){
  182.               six[0]=true;
  183.             }
  184.             amin(a1, priority[n[1]][s]);
  185.           }
  186.           if(!n[1]){
  187.             //opponent's chances
  188.             s=0;
  189.             if(!*pb && !(pe[1]&1) && pb!=comb+4){
  190.               s++;
  191.               if(!*pe && pe!=comb+4) s++;
  192.             }
  193.             if(info_exact5==1 && n[2]==4 && 
  194.               (pe<comb+8 && pe[1]==2 || pb>comb && pb[-1]==2)){
  195.               six[1]=true;
  196.             }
  197.             amin(a2, priority[n[2]][s]);
  198.           }
  199.         }
  200.         n[*++pe]++;
  201.         n[*pb++]--;
  202.       }
  203.     }
  204.     //store computed evaluation to the array
  205.     ind->h[0]= short(six[0] ? 0 : a1);
  206.     ind->h[1]= short(six[1] ? 0 : a2);
  207.     ind++;
  208.   }else{
  209.     //generate last five squares of combination
  210.     for(int z=0; z<4; z++){
  211.       *pos=z;
  212.       gen2(pos+1);
  213.     }
  214.   }
  215. }
  216.  
  217. //generate first four squares of combination
  218. void gen1(int *pos)
  219. {
  220.   if(pos==comb+5){
  221.     gen2(pos);
  222.   }else{
  223.     for(int z=0; z<4; z++){
  224.       *pos=z;
  225.       n[z]++;
  226.       gen1(pos+1);
  227.       n[z]--;
  228.     }
  229.   }
  230. }
  231.  
  232. void gen()
  233. {
  234.   ind=K;
  235.   gen1(comb);
  236. }
  237. //-------------------------------------------------------------------
  238. void init()
  239. {
  240.   int x,y,k;
  241.   Psquare p;
  242.   Tprior *pr;
  243.   
  244.   memset(goodMoves,0,sizeof(goodMoves));
  245.   memset(winMove,0,sizeof(winMove));
  246.   sum[0]= sum[1]= 0;
  247.   
  248.   //alocate the board
  249.   delete[] board;
  250.   height2=height+2;
  251.   board= new Tsquare[(width+10)*(height2)];
  252.   boardb= board + 5*height2;
  253.   boardk= boardb+ width*height2;
  254.   // 5 4 3
  255.   // 6 8 2
  256.   // 7 0 1
  257.   diroff[0]=sizeof(Tsquare);
  258.   diroff[4]=-diroff[0];
  259.   diroff[1]=sizeof(Tsquare)*(1+height2);
  260.   diroff[5]=-diroff[1];
  261.   diroff[2]=sizeof(Tsquare)* height2;
  262.   diroff[6]=-diroff[2];
  263.   diroff[3]=sizeof(Tsquare)*(-1+height2);
  264.   diroff[7]=-diroff[3];
  265.   diroff[8]=0;
  266.   
  267.   //initialize the board
  268.   p=board;
  269.   for(x=-5; x<=width+4; x++){
  270.     for(y=-1; y<=height; y++){
  271.       p->z= (x<0 || y<0 || x>=width || y>=height) ? 3:0;
  272.       p->x= (short)x;
  273.       p->y= (short)y;
  274.       for(k=0;k<2;k++){
  275.         pr=&p->h[k];
  276.         pr->i=0;
  277.         pr->pv=4;
  278.         pr->ps[0]=pr->ps[1]=pr->ps[2]=pr->ps[3]=1;
  279.       }
  280.       p++;
  281.     }
  282.   }
  283.   moves=0;
  284. }
  285. //-------------------------------------------------------------------
  286. //evaluate squares around p0 to distance 4
  287. void evaluate(Psquare p0)
  288. {
  289.  int i,k,m,s,h;
  290.  Tprior *pr;
  291.  Psquare p,q,qk,*up,pe,pk1;
  292.  int *u;
  293.  int ind;
  294.  unsigned pattern;
  295.  static int last_exact5=-1;
  296.  
  297.  if(info_exact5!=last_exact5){
  298.    last_exact5=info_exact5;
  299.    gen();
  300.  }
  301.  //remove not empty square from list and set its evaluation to zero
  302.  if(p0->z){
  303.   for(k=0; k<2; k++){
  304.    pr=&p0->h[k];
  305.    if(pr->pv){
  306.      if(pr->i){
  307.        if((*pr->pre= pr->nxt)!=0) pr->nxt->h[k].pre= pr->pre;
  308.        pr->i=0;
  309.      }
  310.      sum[k]-= pr->pv;
  311.      pr->pv= pr->ps[0]= pr->ps[1]= pr->ps[2]= pr->ps[3]= 0;
  312.    }
  313.   }
  314.  }
  315.  //cycle all directions
  316.  for(i=0; i<4; i++){
  317.   s=diroff[i];
  318.   pk1=p0;
  319.   nxtP(pk1,5);
  320.   pe=p0;
  321.   p=p0;
  322.   for(m=4; m>0; m--){
  323.     prvP(p,1);
  324.     if(p->z==3){
  325.       nxtP(pe,m);
  326.       nxtP(p,1);
  327.       break;
  328.     }
  329.   }
  330.   pattern=0;
  331.   qk=pe;
  332.   prvP(qk,9);
  333.   for(q=pe; q!=qk; prvP(q,1)){
  334.     pattern*=4;
  335.     pattern+=q->z;
  336.   }
  337.   while(p->z!=3){
  338.     if(!p->z){
  339.      for(k=0; k<2; k++){ //both players
  340.       pr= &p->h[k];
  341.       //change evaluation in one direction
  342.       u= &pr->ps[i];
  343.       h= K[pattern].h[k];
  344.       if(info_exact5 && h>=H4){
  345.         if(prvQ(p,5)->z==k+1 && nxtQ(p,1)->z==0 ||
  346.           nxtQ(p,5)->z==k+1 && prvQ(p,1)->z==0){
  347.           h=0;
  348.         }
  349.       }
  350.       m=h-*u;
  351.       if(m){
  352.        *u=h;
  353.        sum[k]+=m;
  354.        pr->pv+=m;
  355.        //choose linked list
  356.        ind=0;
  357.        if(pr->pv >= H21){
  358.         ind++;
  359.         if(pr->pv >= 2*H21){
  360.          ind++;
  361.          if(pr->pv >= H4) ind++;
  362.         }
  363.        }
  364.        //put square to another linked list
  365.        if(ind!=pr->i){
  366.          //remove
  367.          if(pr->i){
  368.            if((*pr->pre= pr->nxt)!=0) pr->nxt->h[k].pre= pr->pre;
  369.          }
  370.          //append
  371.          if((pr->i=ind)!=0){
  372.            up= &goodMoves[ind][k];
  373.            pr->nxt= *up;
  374.            if(*up) (*up)->h[k].pre= &pr->nxt;
  375.            pr->pre= up;
  376.            *up= p;
  377.          }
  378.        }
  379.       }
  380.      }
  381.     }
  382.     nxtP(p,1);
  383.     if(p==pk1) break;
  384.     nxtP(pe,1);
  385.     pattern>>=2;
  386.     pattern+= pe->z << 16;
  387.   }
  388.  }
  389. }
  390. //-------------------------------------------------------------------
  391. int getEval(int player1, Psquare p0)
  392. {
  393.   int i,s,y,c,c1,c2,n,d1,d2;
  394.   Psquare p;
  395.   
  396.   y=0;
  397.   //count symbols on 8 squares around p0
  398.   c1=c2=0;
  399.   for(i=0; i<8; i++){
  400.     s=diroff[i];
  401.     p=p0;
  402.     nxtP(p,1);
  403.     if(p->z==player1+1) c1++;
  404.     if(p->z==2-player1) c2++;
  405.   }
  406.   c=c1+c2;
  407.   if(c==0) y-=20; //too empty
  408.   if(c>4) y-=4*(c-3); //too many
  409.  
  410.   //blocked directions
  411.   d1=d2=0;
  412.   for(i=0; i<4; i++){
  413.     if(p0->h[player1].ps[i]<=1) d1++;
  414.     if(p0->h[1-player1].ps[i]<=1) d2++;
  415.   }
  416.  
  417.   //detect if there is only one player here
  418.   if(c2==0 && c1>0 && p0->h[player1].pv>=H12){
  419.     y+= (c1+1)*5;
  420.   }
  421.   if(d2==4){
  422.     n=0;
  423.     for(i=0; i<4; i++){
  424.       if(p0->h[player1].ps[i]>=H12) n++;
  425.     }
  426.     y+=15;
  427.     if(n>1) y+=n*64;
  428.   }
  429.   return y + p0->h[player1].pv;
  430. }
  431.  
  432.  
  433. int getEval(Psquare p)
  434. {
  435.   int a,b;
  436.   a=getEval(0,p);
  437.   b=getEval(1,p);
  438.   return a>b ? a+b/2 : a/2+b;
  439. }
  440.  
  441. //evaluate all squares in array winMoves
  442. void evalWinMoves()
  443. {
  444.   int Nwins;
  445.   int *e;
  446.   Psquare *t,p;
  447.   
  448.   carefulAttack=true;
  449.   //add high priority squares
  450.   for(p=goodMoves[2][1]; p; p=p->h[1].nxt){
  451.     addWinMove(p);
  452.   }
  453.   //evaluate
  454.   Nwins= UwinMoves-winMoves1;
  455.   assert(Nwins<=MwinMoves);
  456.   for(t=UwinMoves-1,e=winEval+Nwins-1; t!=winMoves1-1; t--,e--){
  457.     *e= getEval(1,*t);
  458.     if(*t==highestEval) *e+=DEFEND_HIGHEVAL;
  459.   }
  460.   //add my chances to make four
  461.   for(p=goodMoves[1][0]; p; p=p->h[0].nxt){
  462.     if(p->h[0].pv<H30) continue;
  463.     addWinMove(p);
  464.     if(p->inWinMoves==UwinMoves-1){
  465.       winEval[Nwins++]= p->h[0].pv>>3;
  466.     }
  467.   }
  468. }
  469.  
  470. //-------------------------------------------------------------------
  471. //find square which has greatest evaluation
  472. //return 0 if evaluation is too low
  473. Psquare findMax()
  474. {
  475.   Psquare p,t;
  476.   int m,r;
  477.   int i,k;
  478.   
  479.   m=-1;
  480.   t=0;
  481.   for(i=2; i>0 && !t; i--){
  482.     for(k=0; k<2; k++){
  483.       for(p=goodMoves[i][k]; p; p=p->h[k].nxt){
  484.         r= getEval(p);
  485.         if(r>m){
  486.           m=r;
  487.           t=p;
  488.         }
  489.       }
  490.     }
  491.   }
  492.   return t;
  493. }
  494.  
  495.  
  496. //find out what total evaluation will be after AHEAD_DEPTH moves
  497. int lookAhead(int player1)
  498. {
  499.   Psquare p;
  500.   int y,i;
  501.   
  502.   if(goodMoves[3][player1]) return 700;
  503.   int player2=1-player1;
  504.   p=goodMoves[3][player2];
  505.   if(!p && dpth<AHEAD_DEPTH) p=findMax();
  506.   if(!p){
  507.     y= sum[0]-sum[1];
  508.     for(i=2; i>0; i--){
  509.       for(p=goodMoves[i][0]; p; p=p->h[0].nxt) y+=NUM_GOOD0;
  510.       for(p=goodMoves[i][1]; p; p=p->h[1].nxt) y-=NUM_GOOD1;
  511.     }
  512.     if(player1) y=-y;
  513.     return int(y/AHEAD_IRRELEVANCE);
  514.   }
  515.   dpth++;
  516.   p->z=player1+1;
  517.   evaluate(p);
  518.   y= -lookAhead(player2);
  519.   p->z=0;
  520.   evaluate(p);
  521.   dpth--;
  522.   return y;
  523. }
  524.  
  525. //-------------------------------------------------------------------
  526.  
  527. DWORD seed= GetTickCount();
  528.  
  529. unsigned rnd(unsigned n)
  530. {
  531.   seed=seed*367413989+174680251;
  532.   return (unsigned)(UInt32x32To64(n,seed)>>32);
  533. }
  534.  
  535. void databaseMove()
  536. {
  537.   signed char *s,*sn;
  538.   Psquare p,k;
  539.   int i,x,y,x1,y1,flip,len1,len2,left,top,right,bottom;
  540.  
  541.   //board rectangle
  542.   for(p=boardb; p->z!=1 && p->z!=2; p++) ;
  543.   left=p->x;
  544.   for(k=boardk; k->z!=1 && k->z!=2; k--) ;
  545.   right=k->x;
  546.   top=bottom=k->y;
  547.   for(; p<k; p++){
  548.     if(p->z==1 || p->z==2){
  549.       amax(top,p->y);
  550.       amin(bottom,p->y);
  551.     }
  552.   }
  553.   //find current board in the database
  554.   for(s=data; ; s=sn){
  555.     len1=*s++;
  556.     len2=*s++;
  557.     sn= s + 2*(len1+len2);
  558.     if(len1!=moves){
  559.       if(len1<moves) return;
  560.       continue;
  561.     }
  562.     //try all symmetries
  563.     for(flip=0; flip<8; flip++){
  564.       for(i=0; ;i++){
  565.         x1=s[2*i];
  566.         y1=s[2*i+1];
  567.         if(i==len1){
  568.           s += 2*(len1+rnd(len2));
  569.           x1=*s++;
  570.           y1=*s;
  571.         }
  572.         switch(flip){
  573.         case 0: x=left+x1; y=top+y1; break;
  574.         case 1: x=right-x1; y=top+y1; break;
  575.         case 2: x=left+x1; y=bottom-y1; break;
  576.         case 3: x=right-x1; y=bottom-y1; break;
  577.         case 4: x=left+y1; y=top+x1; break;
  578.         case 5: x=right-y1; y=top+x1; break;
  579.         case 6: x=left+y1; y=bottom-x1; break;
  580.         default: x=right-y1; y=bottom-x1; break;
  581.         }
  582.         p=Square(x,y);
  583.         if(i==len1){
  584.           doMove(p);
  585.           return;
  586.         }
  587.         if(p->z != 2-(i&1)) break;
  588.       }
  589.     }
  590.   }
  591. }
  592.  
  593. void firstMove()
  594. {
  595.   //the first move is in the middle of the board
  596.   if(moves==0){
  597.     doMove(Square(width/2+rnd(5)-2,height/2+rnd(5)-2));
  598.     return;
  599.   }
  600.   if(moves==2){
  601.     Psquare p;
  602.     for(p=boardb; p->z!=1; p++) ;
  603.     doMove(nxtS(p,rnd(8)));
  604.   }
  605.   databaseMove();
  606.   //already four in a line -> don't think
  607.   if(goodMoves[3][0] && (!info_continuous || !goodMoves[3][0]->h[0].nxt || !goodMoves[3][1])){
  608.     if(doMove(goodMoves[3][0])) return; //I win
  609.   }
  610.   doMove(goodMoves[3][1]); //I have to defend
  611. }
  612.  
  613.  
  614. //find square which has very good evaluation
  615. void getBestEval()
  616. {
  617.   int i,r,m,d,a,b;
  618.   Psquare p,bestMove;
  619.   int Nresults=0;
  620.  
  621.   bestMove=0;
  622.   if(moves>9){
  623.     m=-0x7ffffffe;
  624.     for(p=boardb; p<boardk; p++){
  625.       if(!p->z && (p->h[0].pv>10 || p->h[1].pv>10)){
  626.         a=getEval(0,p);
  627.         b=getEval(1,p);
  628.         r= (a>b) ? int((a + b/2)*OFFENSIVE) : (a/2 + b);
  629.         p->z=1;
  630.         evaluate(p);
  631.         r-= lookAhead(1);
  632.         p->z=0;
  633.         evaluate(p);
  634.         if(r>m){
  635.           m=r;
  636.           bestMove=p;
  637.           Nresults=1;
  638.         }else if(r>m-EVAL_RAND1){
  639.           Nresults++;
  640.           if(!rnd(Nresults)) bestMove=p;
  641.         }
  642.       }
  643.     }
  644.   }
  645.   if(!bestMove){
  646.     m=-0x7fffff;
  647.     for(p=boardb; p<boardk; p++){
  648.       if(!p->z){
  649.         r=getEval(p);
  650.         if(r>m) m=r;
  651.       }
  652.     }
  653.     d= abs(m/12);
  654.     amax(d,EVAL_RAND2);
  655.     Nresults=0;
  656.     for(p=boardb; p<boardk; p++){
  657.       if(!p->z){
  658.         if(getEval(p) >= m-d){
  659.           Nresults++;
  660.           if(!rnd(Nresults)) bestMove=p;
  661.         }
  662.       }
  663.     }
  664.   }
  665.   doMove(bestMove);
  666.   highestEval=bestMove;
  667.   
  668.   if(lastMove){
  669.     p=lastMove;
  670.     for(i=0; ; i++){
  671.       if(i==8){
  672.         //opponent made an isolated move -> defend it
  673.         doMove(nxtS(p,rnd(8)));
  674.         break;
  675.       }
  676.       if(nxtS(p,i)->h[1].ps[i&3]!=H12) break;
  677.     }
  678.   }
  679. }
  680.  
  681. //-------------------------------------------------------------------
  682.  
  683. void computer1()
  684. {
  685.   int y=0;
  686.   const int player1=0, player2=1;
  687.   
  688.   if(loss4){
  689.     winMove[player2]=loss4;
  690.     winMoveDepth[player2]=10;
  691.     y=-1;
  692.   }
  693.   bestMove=0;
  694.   //attack
  695.   if(!attackDone && (!loss4 || winMove[player1])){ 
  696.     #ifdef DEBUG
  697.       print(carefulAttack ? "attack2":"attack");
  698.     #endif
  699.     depthReached=false;
  700.     //I have already found win
  701.     if(winMove[player1]){
  702.       y= alfabeta(carefulAttack,1,player1,0,winMove[player1]);
  703.       if(y<=0){
  704.         if(winMoveDepth[player1]<=depth) winMove[player1]= 0;
  705.       }
  706.     }
  707.     if(!bestMove){
  708.       y= alfabeta(carefulAttack,1,player1,0);
  709.     }
  710.     if(y>0 && bestMove){
  711.       doMove(bestMove);
  712.       winMove[player1]=bestMove;
  713.       winMoveDepth[player1]=depth;
  714.       #ifdef DEBUG
  715.         if(!terminate) resulty=y;
  716.       #endif
  717.       if(!carefulAttack){
  718.         carefulAttack=true;
  719.       }else{
  720.         terminate=3; //win
  721.       }
  722.       return;
  723.     }                 
  724.     if(!depthReached) attackDone=true; 
  725.   }
  726.   //find out if opponent can win
  727.   if(UwinMoves==winMoves1 && !testDone){ 
  728.     #ifdef DEBUG
  729.       print("thinking");
  730.     #endif
  731.     depthReached=false;
  732.     y=0;
  733.     if(winMove[player2]){
  734.       y= alfabeta(0,1,player2,1,winMove[player2]);
  735.       if(y<=0){ 
  736.         if(winMoveDepth[player2]<=depth) winMove[player2]=0; 
  737.         UwinMoves=winMoves1; 
  738.       }
  739.     }
  740.     if(y<=0){
  741.       y= alfabeta(0,1,player2,1);
  742.       if(y>0){ 
  743.         winMove[player2]=bestMove; 
  744.         winMoveDepth[player2]=depth;
  745.       }else{
  746.         UwinMoves=winMoves1; 
  747.       }    
  748.     }
  749.     if(y>0) evalWinMoves(); 
  750.     if(!depthReached) testDone=true;
  751.   }
  752.   
  753.   //defend
  754.   if(UwinMoves>winMoves1 && !defendDone &&
  755.     (!defendDone1 || carefulDefend)){ 
  756.     #ifdef DEBUG
  757.       print(carefulDefend ? "defend2":"defend"); 
  758.     #endif
  759.     depthReached=false;
  760.     bestMove=0;
  761.     y=defend();
  762.     if(!bestMove){   
  763.       y=alfabeta(1,0,player1,0);
  764.     } 
  765.     #ifdef DEBUG
  766.       if(y<=0 && !terminate) resulty=y;
  767.     #endif
  768.     if(!depthReached){
  769.       if(!carefulDefend) defendDone1=true; 
  770.       else defendDone=true;
  771.     }
  772.     if(y<0) carefulDefend=true;
  773.     doMove(bestMove);
  774.   }
  775.   assert(dpth==0);
  776. }
  777.  
  778.